/**
 * 分隔链表
 *
 * 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
 * 你应当 保留 两个分区中每个节点的初始相对位置。
 *
 * 示例 1：
 * 输入：head = [1,4,3,2,5,2], x = 3
 * 输出：[1,2,2,4,3,5]
 *
 * 示例 2：
 * 输入：head = [2,1], x = 2
 * 输出：[1,2]
 *
 * 提示：
 * 链表中节点的数目在范围 [0, 200] 内
 * -100 <= Node.val <= 100
 * -200 <= x <= 200
 */

/**
 * 用两个链表分别来存储大于 x 和 小于 x 的节点, 最后在将两个链表进行合并就可以了
 * 这里要求的原顺序就是 小于 x 的节点在新的链表中要按照原来的顺序进行插入
 *                  大于 x 的节点在新的链表中要按照原来的顺序进行插入
 * 时间复杂度 : O(n)
 * 空间复杂度 : O(1)
 */

public class Main {
    public ListNode partition(ListNode head, int x) {

        // 链表头结点
        ListNode small = new ListNode(0);
        ListNode big = new ListNode(0);

        // 打工节点, 最后分别指向两个链表的尾节点
        ListNode smallHead = small;
        ListNode bigHead = big;

        // 遍历链表
        while (head != null) {

            if (head.val < x) {
                small.next = head;
                small = small.next;
            } else {
                big.next = head;
                big = big.next;
            }

            head = head.next;
        }

        // 连接两个链表
        small.next = bigHead.next;

        // 这里不要忘记将最后的链表尾节点 下一个节点 指向 null
        big.next = null;

        return smallHead.next;
    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}